In two-dimensional model based image coding, an image is partitioned into connected two-dimensional discrete domains, each modeled with its own polynomial intensity function. The two components of such a code are a description of the domain boundaries and a description of the polynomial intensity unctions. The descriptions are typically separate, with each domain's boundary description occurring before its polynomial intensity function in a coded bit stream.
Two-dimensional model based coding is a form of lossy image coding, where the coded image is not identical to its source. The distortion of a coded image measures the degree to which it differs from its source image. The rate of a coded image is the length of its coded description in bits divided by its pixel count. A low distortion encoding has a relatively higher rate than a high distortion encoding of the same source, but it more closely matches the source.
For a lossy coding scheme to have general applicability, it must be able to smoothly trade rate for distortion. A two-dimensional model based coder typically trades rate for distortion by altering the number of domains in the image model. However, this mechanism is not able to fully take advantage of the properties of the human visual system that make it more sensitive to certain types of errors than others. For example, the visual property known as intensity masking makes it more difficult for a human observer to distinguish between two slightly different relatively dark areas of an image if they abut a relatively bright area than if they abut only other relatively dark areas. The variable visual sensitivity to spatial frequency makes it more difficult for an observer to discern intensity changes in highly textured or large gradient regions of an image than in relatively smooth regions.
Since the domains of a two-dimensional image model typically are significantly aligned with image features, a natural way to take advantage of human visual system properties is to represent the polynomial intensity unctions of some domains more accurately than others. Of course to make this technique useful, a method for trading rate for polynomial distortion must be available.
One polynomial description appropriate for trading rate for distortion is a sequence of samples of the generated surface. A critical sampling makes only one sample per term of the generating polynomial and is most applicable to coding. An n term polynomial surface is recovered from n samples by solving a simultaneous system of n equations and n unknowns. For example, a planar surface EQU z(x,y)=ax+by+c (1)
can be recovered from three sample points (x.sub.n,y.sub.n,z.sub.n), by solving the system of equations ##EQU1## for the unknown coefficients a, b, and c.
Given appropriate sample (x,y) coordinates or locations, the accuracy of a polynomial surface recovered from samples is proportional to the accuracy of the sample z coordinates or values. A natural way to trade polynomial descriptive bits for image distortion is to quantize the sample values representing each polynomial surface. Quantized samples can take on only a relatively small number of values. Coarsely quantized samples have fewer possible values than finely quantized samples. As quantization becomes more coarse, the number of bits necessary to represent each value decreases. Distortion is increased, however, since the polynomial surface recovered from coarsely quantized values is likely to be an inferior intensity function compared to the surface from which the samples were taken.
In order that fixed point numbers may be used to represent quantized values, it is desirable to fix their dynamic range. In two-dimensional model based codes the polynomial intensity functions commonly used are interpolating polynomials. Therefore, samples of a polynomial intensity function taken within its associated domain are guaranteed to lie within the dynamic range of the of the image. For example, samples of a surface interpolating a 256 level grayscale image are guaranteed to fit into unsigned eight bit integers. Samples of such a surface made just outside its interpolating region are not so guaranteed.
To recover a polynomial surface from quantized samples, at least three types of information must be available: the polynomial terms to be recovered, sample locations and sample values. In order to effectively trade rate for distortion, the major part of a coded polynomial description must consist of sample values. Conversely, the other two parts of a coded description, the polynomial terms to be recovered and the sample locations, must have a minimal descriptive length.
In two-dimensional model based codes, the recoverable polynomial terms are frequently restricted to a small number of sets determined by the largest exponent. Commonly used sets are the maximal polynomials of a given integer order. Such polynomials consist of all possible terms with combined power of x and y less than or equal to the corresponding order. The first four maximal two-dimensional polynomials are comprised of one, three, six and ten terms respectively. Due to the restriction on the number of possible polynomials, the number of bits necessary to code the polynomial terms to be recovered for each domain is rather small. Further, it is common for a single polynomial order to apply to every domain of a coded description. In such cases, the number of bits necessary to specify the recoverable terms of each polynomial is effectively zero.
It is desirable to also reduce the number of bits necessary for describing sample locations to zero. One way this might be accomplished is to infer sample locations from other information the coded description. In an encoded two dimensional image model the relevant information available for inferring appropriate sample locations consists of polynomial order and domain shape. If domains are allowed to take on only certain shapes, several fixed regular sampling patterns may be applicable. However, for freeform domains a small number of sampling patterns is inadequate since some samples will invariably fall outside of their associated domain. Sample values at such locations are not guaranteed to lie within the dynamic range of the image. A freeform domain may also have an inappropriate shape to support all the terms of a given maximal polynomial order. For example, a domain that is only one pixel wide cannot support polynomial terms containing x, or a domain that is only one pixel tall cannot support terms in y.
Therefore, there is a need for a method for implicitly determining appropriate locations within a freeform two-dimensional domain at which to sample a polynomial surface over the domain such that when the surface is recovered from the samples it is both accurate and minimally sensitive to changes in sample values. The method should determine sample locations solely from domain shape and maximal polynomial order. The number of sample locations should be nominally equivalent to the number of terms of the polynomial generating the surface but should be reduced if appropriate locations cannot be found.